#pragma once

#include <cstdint>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>

#include "parser.h"


namespace parser {

/**
 * Type Definitions
 */

// a rule is a Vn(char) -> expression(string)
using Rule = std::pair<char, std::string>;
// assume that table storage sample (A -> α) is:
//   HashMap[ (A,α) -> i ]
// where i is index of rule 'A -> α' in syntax rules, 'A' is row, 'α' is column.
// here we compress 'A' and 'α' into an uint16_t variable.
using PredictKey = uint16_t;
using PredictTable = std::unordered_map<PredictKey, int>;

struct SyntaxRule 
{
    std::unordered_set<char> vns;       // non-terminal
    std::unordered_set<char> vts;       // terminal
    std::vector<Rule>        rules;     // generation expressions
    char                     epsilon;   // ε means empty word
    char                     start;     // Start symbol (non-terminal)
};

// for each symbol we have s struct to store 3 kinds of sets
struct SymbolSet 
{
    std::unordered_set<char> first_set;
    std::unordered_set<char> follow_set;
    std::unordered_set<char> select_set;
    bool first_has_empty;
};

// All Symbol Sets is a HashMap: symbol(char) -> SymbolSet
using SymbolSets = std::unordered_map<char, SymbolSet>;


/**
 * PredictParser Class Definition
 */

class PredictParser : public Parser
{
public:
    PredictParser(SyntaxRule& s) : syntax(s) {};
    void Parse(std::string &expression) override;

private:
    // predict method function definitions.
    void ExtractCommonFactors();
    void RemoveLeftRecursion();
    void GetFirstSet(char symbol, std::unordered_set<char> &first);
    void GetFollowSet(char symbol, std::unordered_set<char> &follow);
    void MakePredictTable();

private:
    SyntaxRule      syntax;
    SymbolSets      symbol_sets;
    PredictTable    table;
};


} // namespace pred

